package cn.xaut.周赛.m226;

/**
 * 5. 最长回文子串
 */
public class demo5 {

    static boolean isPalindrome(String s) {

        int i = 0, j = s.length() - 1;
        int n = s.length();
        if (n == 1)
            return true;
        if (n == 2)
            return s.charAt(i) == s.charAt(j);

        return s.charAt(i) == s.charAt(j) && isPalindrome(s.substring(i + 1, j));
    }

    // 暴力解法1
    public String longestPalindrome(String s) {

        int n = s.length();
        if (n == 1)
            return s;

        String res = s.substring(0, 1);
        int size = 1;
        for (int i = 0; i < n; i ++) {
            for (int j = i + 1; j <= n; j ++) {
                String substring = s.substring(i, j);
                if (substring.length() > size && isPalindrome(substring)) {
                    res = substring;
                    size = substring.length();
                }
            }
        }
        return res;
    }

    // 暴力解法2    
    // 从中间向两边扩散
    public String longestPalindrome2(String s) {
        
        int n = s.length();
        if (n == 1)
            return s;

        String res = "";
        int size = 0;
        // 奇数串
        for (int i = 0; i < n; i++) {
            int l = i, r = i + 1;
            while (l >= 0 && r <= n) {
                String substring = s.substring(l, r);
                if (!isPalindrome(substring))
                    break;  
                if (substring.length() > size) {
                    res = substring;
                    size = substring.length();
                }
                l --;
                r ++;
            }
        }
        // 偶数串
        for (int i = 0; i < n; i++) {
            int l = i, r = i + 1;
            while (l >= 0 && r < n) {
                String substring = s.substring(l, r + 1);
                if (!isPalindrome(substring))
                    break;
                if (substring.length() > size) {
                    res = substring;
                    size = substring.length();
                }
                l --;
                r ++;
            }
        }
        return res;
    }

    // todo: 动态规划
    public String longestPalindrome3(String s) {
        
        int len = s.length();
        if (len < 2)
            return s;
        
        int maxLen = 1, begin = 0;
        // dp[i][j] 表示 s[i...j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) 
            dp[i][i] = true;
        
        char[] charArray = s.toCharArray();
        // 注意：左下角先填
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                
                if (charArray[i] == charArray[j]) {
                    if (j - i < 3)    // 字符串的长度为 1 或 2
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];
                } else {    
                    dp[i][j] = false;
                }

                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    public static void main(String[] args) {

        System.out.println(new demo5().longestPalindrome3("babad"));
        System.out.println(new demo5().longestPalindrome3("cbbd"));
        System.out.println(new demo5().longestPalindrome3("a"));
        System.out.println(new demo5().longestPalindrome3("ac"));
    }
}
